import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public boolean isBalanced(TreeNode root) {
        //空树也是平衡二叉树
        if(root==null){
            return true;
        }
        return getHeight(root)>=0;
    }

    public int getHeight(TreeNode root){

        if(root==null){
            return 0;
        }

        int leftH=getHeight(root.left);

        if(leftH<0){
            return-1;
        }

        int rightH=getHeight(root.right);

        if(rightH<0){
            return-1;
        }

        if(leftH>=0&&rightH>=0&&Math.abs(leftH-rightH)<=1){
            return leftH>rightH ? leftH+1:rightH+1;
        }else{
            return -1;
        }

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode ret1=lowestCommonAncestor(root.left,p,q);
        TreeNode ret2=lowestCommonAncestor(root.right,p,q);
        if(ret1!=null&&ret2!=null){
            return root;

        }else if(ret1!=null){
            return ret1;
        }else{
            return ret2;
        }
    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret=new LinkedList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer> ret1=new LinkedList<>();
            while(size!=0){
                TreeNode cur=queue.poll();
                ret1.add((int) cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(0,ret1);
        }
        return ret;

    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new LinkedList<>();
        if(root==null){
            return ret;
        }

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int size=queue.size();
            List<Integer> ret1=new LinkedList<>();

            while(size!=0){
                TreeNode cur=queue.poll();
                ret1.add((int) cur.val);

                if(cur.left!=null){
                    queue.offer(cur.left);

                }

                if(cur.right!=null){
                    queue.offer(cur.right);

                }
                size--;
            }
            ret.add(ret1);
        }
        return ret;
    }
    public String tree2str(TreeNode root){

        //new 一个stringBuilder 去存储我遍历二叉树的值

        StringBuilder stringBuilder=new StringBuilder();

        tree2strChild(root,stringBuilder);

        return stringBuilder.toString();

    }

    public void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if (root==null){
            return;
        }

        stringBuilder.append(root.val);

        //判段root的左子树和右子树是否为空

        //左子树

        if (root.left!=null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");

        }
        else {
            if (root.right==null){
                //root的左树，右树都为空
                return;
            }

            else {
                stringBuilder.append("()");
            }

        }

        //右子树

        if (root.right!=null){
            stringBuilder.append("(");
            tree2strChild(root.right, stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
}
